package HuaWei;

/**
 * @author fly
 * @create 2021--04--17--15:00
 */
public class safe1 {
    public static void main(String[] args) {
        String s="aaab";
        String p="ab";
        StringBuilder sb=new StringBuilder(s);
        StringBuilder sp=new StringBuilder(p);
        int ans=0;
        while(find(s,p)!=-1){
            int idx=find(s,p);
            sb.delete(idx,idx+2);
            sb.insert(idx,"bba");
            s=sb.toString();
            ans++;
        }
        System.out.println(ans);
    }

    public static int find(String s,String p){
        int n=s.length();
        int m=p.length();
        s=' '+s;
        p=' '+p;

        int[] next=new int[m+1];
        for(int i=2,j=0;i<=m;i++){
            while(j>0&&p.charAt(j+1)!=p.charAt(i))j=next[j];
            if(p.charAt(i)==p.charAt(j+1))j++;
            next[i]=j;
        }

        for(int i=1,j=0;i<=n;i++){
            while(j>0&&s.charAt(i)!=p.charAt(j+1))j=next[j];
            if(s.charAt(i)==p.charAt(j+1))j++;
            if(j==m){
                return i-m;
            }
        }
        return -1;
    }
}
